package solution1.demo.demo5;

  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

public class Solution {
//      //1.移除链表元素
//      public ListNode removeElements(ListNode head, int val) {
//          ListNode dummy = new ListNode();
//          dummy.next = head;
//          ListNode prev = dummy;
//            ListNode cur = head;
//            while(cur != null) {
//                if(cur.val == val) {
//                    prev.next = cur.next;
//                    cur = cur.next;
//                    continue;
//                }
//                prev = cur;
//                cur = cur.next;
//            }
//            return dummy.next;
//      }
//
////      //2.反转链表
////    public ListNode reverseList(ListNode head) {
////        if(head == null) {
////            return head;
////        }
////        ListNode dummy = new ListNode();
////        dummy.next = head;
////        ListNode prev = dummy;
////        ListNode cur = head;
////        ListNode curNext = cur.next;
////        while(cur.next != null) {
////            cur.next = prev;
////            prev = cur;
////            cur = curNext;
////            curNext = curNext.next;
////        }
////        //去除虚拟结点
////        dummy.next.next = null;
////        return cur;
////    }
//
//    //3.翻转链表(优化)
//    public ListNode reverseList(ListNode head) {
//        if(head == null) {
//            return null;
//        }
//        ListNode cur = head.next;
//        head.next = null;
//        while(cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = curNext;
//        }
//        return head;
//    }
//
//    //4.两两交换链表中的节点
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null) {
//            return head;
//        }
//        ListNode dummy = new ListNode();
//        ListNode prev = dummy;
//        ListNode cur = head;
//        while(cur != null && cur.next != null) {
//            ListNode curNext = cur.next;
//            prev.next = curNext;
//            cur.next = curNext.next;
//            curNext.next = cur;
//            prev = cur;
//            cur = cur.next;
//        }
//        return dummy.next;
//    }
//
//    //5.删除链表的倒数第 N 个结点
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if(head == null) {
//            return null;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode dummy = new ListNode();
//        dummy.next = head;
//        ListNode prev = dummy;
//        //快指针先走n
//        for(int i = 0; i < n; i++) {
//            fast = fast.next;
//        }
//        //同时走
//        while(fast != null) {
//            prev = slow;
//            fast = fast.next;
//            slow = slow.next;
//        }
//        prev.next = slow.next;
//        slow.next = null;
//        return dummy.next;
//    }
//
//    //6.面试题 02.07. 链表相交
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode cur1 = headA;
//        ListNode cur2 = headB;
//        int len1 = 0;
//        int len2 = 0;
//        while(cur1 != null) {
//            cur1 = cur1.next;
//            len1++;
//        }
//        while(cur2 != null) {
//            cur2 = cur2.next;
//            len2++;
//        }
//        cur1 = headA;
//        cur2 = headB;
//        if(len1 > len2) {
//            int ans = len1 - len2;
//            while(ans > 0) {
//                cur1 = cur1.next;
//                ans--;
//            }
//            while(cur1 != null && cur2 != null) {
//                if(cur1 == cur2) {
//                    break;
//                }
//                cur1 = cur1.next;
//                cur2 = cur2.next;
//            }
//            return cur1;
//        } else {
//            int ans = len2 - len1;
//            while(ans > 0) {
//                cur2 = cur2.next;
//                ans--;
//            }
//            while(cur1 != null && cur2 != null) {
//                if(cur1 == cur2) {
//                    break;
//                }
//                cur1 = cur1.next;
//                cur2 = cur2.next;
//            }
//            return cur1;
//        }
//    }
//
//    //7.环形链表(II)
//    public ListNode detectCycle(ListNode head) {
//        if(head == null || head.next == null) {
//            return null;
//        }
//        ListNode fast = head.next.next;
//        ListNode slow = head.next;
//        while(fast != null && fast.next != null && slow != null && fast != slow) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //非环形
//        if(fast == null || slow == null) {
//            return null;
//        }
//        ListNode cur = head;
//        while(slow != null && cur != null && slow != cur) {
//            slow = slow.next;
//            cur = cur.next;
//        }
//        if(slow == null || cur == null) {
//            return null;
//        }
//        return cur;
//    }
//
//
//    private ListNode fan(ListNode head) {
//        ListNode cur = head.next;
//        head.next = null;
//        while(cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = curNext;
//        }
//        return head;
//    }
//
//    //8.回文链表
//    public boolean isPalindrome(ListNode head) {
//        if(head.next == null) {
//            return true;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode prev = head;
//        while(fast != null && fast.next != null) {
//            prev = slow;
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //翻转链表
//        ListNode cur1 = fan(slow);
//        ListNode cur2 = head;
//        while(cur1 != null && cur2 != null) {
//            if(cur1.val != cur2.val) {
//                return false;
//            }
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//        }
//        return true;
//    }

    //9.重排链表
    private ListNode reverseList(ListNode head) {
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public void reorderList(ListNode head) {
        //从中分割链表
        if(head.next == null) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        while(fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        prev.next = null;
        //翻转分割后者链表
        ListNode headNext = reverseList(slow);
        //合并链表
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(cur != null && head != null) {
            cur.next = head;
            cur = cur.next;
            head = head.next;
            cur.next = headNext;
            cur = cur.next;
            headNext = headNext.next;
        }
        if(head != null) {
            cur.next = head;
        }
        if(headNext != null) {
            cur.next = headNext;
        }
        head = dummy.next;
    }

    // 10.两两交换链表中的节点(优化)
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        ListNode prev = dummy;
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = cur;
            prev.next = curNext;
            prev = cur;
            cur = cur.next;
        }
        return dummy.next;
    }

}

class Main {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        Solution solution = new Solution();
        solution.reorderList(node1);
    }
}
